/*
 * 对于一个包含不重复整数的数组 array [1, 2, 3]
 * Power Set: array 子集的数组
 * [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
 * 
 * 1. 不能重复
 * 2. 不能漏掉
 * [1, 4]
 * 
 * 编写一个函数，让它接受一个整数数组作为参数，并返回它的 power set。
 */

#include <vector>
#include <iostream>

using namespace std;

/* [1, 2, 3]
 * [[]]
 * [[], [1]] 每拿到一个数字，就和答案中的每一个元素组合，形成新的答案
 * 
 * 
 *  
 * [[], [1], [2], [1, 2]] 
 * [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] <- 当前的 power set
 */
vector<vector<int>> powerSet(vector<int> array) {
  vector<vector<int>> result {{}};

  for (int number : array) {
    int length = result.size();

    for (int i = 0; i < length; ++i) {
      // v []
      // tmp []
      // tmp [2]
      // [[], [1], [2], [1, 2]]
      vector<int> tmp = result[i];
      tmp.push_back(number);

      result.push_back(tmp);
    }  
  }

  return result;
}

// clang++ -std=c++17 PowerSet.cpp -o output/PowerSet
int main(int argc, char const *argv[]) {
  vector<int> value {1, 2, 3};
  vector<vector<int>> result = powerSet(value);

  for (vector<int> v : result) {
    cout<<"[";

    for (int n : v) {
      cout<<n<<",";
    }

    cout<<"]";
  }
  
  return 0;
}
